#include "Search.h"
/*
 * The simplest situation.
 * The searched array has no duplicated data, and is sorted.
 *
 */
#ifdef _DEBUG
int binarySearch(int arr[], int n, int value, int *cnt)
#else
int binarySearch(int arr[], int n, int value)
#endif
{
    if(n <= 1 || arr == nullptr)
        return -1;

    int low = 0, high = n - 1;
    int mid = 0;

    #ifdef _DEBUG
    int cmp_cnt = 0;
    #endif

    while(low <= high)
    {
        /* if @low and @ high are very great number, 
         * their addition may cause overflow.
         */
        // mid = (low + high) / 2; 
        
        mid = low + ((high - low) >> 1);

    #ifdef _DEBUG
        cmp_cnt++;
    #endif 
        if(value > arr[mid])
        {
            low = mid + 1;
        }
        else if(value < arr[mid])
        {
            high = mid - 1;
        }
        else
        {
    #ifdef _DEBUG
            if(cnt != nullptr)
                *cnt = cmp_cnt;
    #endif
            return mid;
        }
    }


#ifdef _DEBUG
    if (cnt != nullptr)
        *cnt = -1;
#endif
    return -1;

}

static int binary_search_inter(int arr[], int low, int high, int value)
{
    if (low > high)
        return -1;

    int mid = low + ((high - low) >> 1);

    if (value > arr[mid])
        return binary_search_inter(arr, mid + 1, high, value);
    else if (value < arr[mid])
        return binary_search_inter(arr, low, mid - 1, value);
    else
        return mid;
}
/* Implementation in recursive style */
#ifdef _DEBUG
int binarySearch2(int arr[], int len, int value, int *cnt)
{
    (void)cnt;
    return binary_search_inter(arr, 0, len - 1, value);
}
#else
int binarySearch2(int arr[], int len, int value)
{
    return binary_search_inter(arr, 0, len - 1, value);
}
#endif

/*
 * Binary Search Variant 1
 * The array has some duplicated data, and is sorted.
 * We search for the first element equal to @value
 */
static int binary_search_var1_inter(int arr[], int len, int value)
{
    if(len <= 1 || arr == nullptr)
        return -1;

    int low = 0, high = len - 1;
    int mid = 0;
   
    while(low <= high)
    {
        mid = low + ((high - low) >> 1);

        if(value > arr[mid])
        {
            low = mid + 1;
        }
        else if(value < arr[mid])
        {
            high = mid - 1;
        }
        else 
        {
            if(mid == 0 || arr[mid-1] != value)
                return mid;
            else
                high = mid - 1;
        }
    }

    return -1;
}

#ifdef _DEBUG
int binarySearchVar1(int arr[], int len, int value, int *cnt)
{
    (void)cnt;
    return binary_search_var1_inter(arr, len, value);
}
#else
int binarySearchVar1(int arr[], int len, int value)
{
    return binary_search_var1_inter(arr, len, value);
}

#endif

